package leetcode._05_二叉树;

import org.junit.Test;

import java.util.LinkedList;
import java.util.Queue;

/**
 * @author pppppp
 * @date 2022/3/30 15:08
 * 给了二叉树的后序遍历 和 中序，求层序遍历。输入,CBEFDA , CBAEDF，输出应该是ABDCEF
 */
public class 求层序遍历 {

    @Test
    public void T_0() {
        String[][] s = {{ "CBEFDA","CBAEDF",}};
        String[] ans = {"ABDCEF"};
        for (int i = 0; i < s.length; i++) {
            NodeX nodeX = buildTree(s[i][0], s[i][1]);
            StringBuilder sb = new StringBuilder(nodeX.val);
            /*层序遍历*/
            Queue<NodeX> queue = new LinkedList<>();
            queue.add(nodeX);
            while (!queue.isEmpty()){
                NodeX poll = queue.poll();
                sb.append(poll.val);
                if(poll.left != null){
                    queue.add(poll.left);
                }
                if(poll.right != null){
                    queue.add(poll.right);
                }
            }
            System.out.println(sb.toString().equals(ans[i]));
        }
    }


    public NodeX buildTree(String postorder, String inorder) {
        if(postorder.length() == 0){
            return null;
        }
        if(postorder.length() == 1){
            return new NodeX(postorder.charAt(0));
        }

        char rootC = postorder.charAt(postorder.length() - 1);
        NodeX root = new NodeX(rootC);
        int inorderIndex = inorder.indexOf(rootC);
        String postorderL = postorder.substring(0, inorderIndex);
        String inorderL = inorder.substring(0, inorderIndex);
        String postorderR = postorder.substring(inorderIndex,postorder.length() - 1);
        String inorderR = inorder.substring(inorderIndex + 1);

        root.left = buildTree(postorderL, inorderL);
        root.right = buildTree(postorderR, inorderR);
        return root;
    }
}

class NodeX {
    char val;
    public NodeX left;
    public NodeX right;

    NodeX() {
    }

    public NodeX(char val) {
        this.val = val;
    }

    NodeX(char val, NodeX left, NodeX right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}
